package chapter07;

public class Triangles {
    static int n;
    static int half;
    static int count;
    static int[][] p;
    static long  sum;
    public static long compute(int n){
        Triangles.n=n;
        count=0;
        sum=0;
        half=n*(n+1)/2;
        if(half % 2 == 1)
            return 0;
        half=half/2;
        p=new int[n+1][n+1];
        for (int i = 0; i <=n; i++) {
            for (int j = 0; j <=n ; j++) {
                p[i][j]=0;
            }
        }
        backtrack(1);

        return sum;
    }
    private static void backtrack(int t){
        if((count>half)||(t*(t-1)/2-count > half)){
            return;
        }
        if(t>n){
            sum++;
        }else {
            for (int i = 0; i < 2; i++) {
                p[1][t]=i;
                count+=i;
                //计算新增边的其余各点
                for (int j = 2; j <= t ; j++) {
                    p[j][t-j+1]=(p[j-1][t-j+1]^p[j-1][t-j+2]) == 1 ? 0 : 1;
                    count+=p[j][t-j+1];

                }
                backtrack(t+1);
                for (int j = 2; j <=t ; j++) {
                    count-=p[j][t-j+1];

                }
                count-=i;
            }
        }
    }

    public static void main(String[] args) {
        long r=Triangles.compute(8);
        System.out.println(r);
    }

}
